package com.data.algorithm.sort;

/**
 * 插入排序
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/3/6
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[80000];

        for(int i = 0; i < 80000; ++i) {
            arr[i] = (int)(Math.random() * 8000000.0D);
        }

        Long startTime = System.currentTimeMillis();
        System.out.println("开始排序");
        insertSort(arr);
        Long endTime = System.currentTimeMillis()- startTime;

        System.out.println("排序耗时：" + endTime+"毫秒");
        System.out.println("排序耗时：" + endTime/1000+"秒");
    }

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr) {

        int insertVal ;
        int insertIndex;

        for(int i = 1; i < arr.length; ++i) {

            insertVal = arr[i];
            for(insertIndex = i - 1; insertIndex >= 0 && insertVal < arr[insertIndex]; --insertIndex) {
                arr[insertIndex + 1] = arr[insertIndex];
            }

            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }

    }
}

